#ifndef UUID_F41E4A110DB24E636A5271A33C937B46
#define UUID_F41E4A110DB24E636A5271A33C937B46

#include <cassert>
#include <cstdio>

#include "common.hpp"
#include "bit_model.hpp"

struct ByteModelBitwise
{
	BitModelFast models[256];
	
	template<typename Coder>
	void encode(Coder& e, int c)
	{
		// code high 4 bits in contexts cxt+1..15
		int b = (c>>4) + 16;

		e.encode(b>>3&1, models[1].p());
		e.encode(b>>2&1, models[b >> 3].p());
		e.encode(b>>1&1, models[b >> 2].p());
		e.encode(b   &1, models[b >> 1].p());

		models[1     ].update(b>>3&1);
		models[b >> 3].update(b>>2&1);
		models[b >> 2].update(b>>1&1);
		models[b >> 1].update(b   &1);

		BitModelFast* lower = &models[15*(b-15)];

		b = (c&15) + 16;
		e.encode(b>>3&1, lower[1].p());
		e.encode(b>>2&1, lower[b >> 3].p());
		e.encode(b>>1&1, lower[b >> 2].p());
		e.encode(b   &1, lower[b >> 1].p());

		lower[1     ].update(b>>3&1);
		lower[b >> 3].update(b>>2&1);
		lower[b >> 2].update(b>>1&1);
		lower[b >> 1].update(b   &1);
	}

	template<typename Decoder>
	int decode(Decoder& e)
	{
		// code high 4 bits in contexts cxt+1..15
		int hi = 1, lo = 1;

		hi += hi + e.decode(models[1].p());
		hi += hi + e.decode(models[hi].p());
		hi += hi + e.decode(models[hi].p());
		hi += hi + e.decode(models[hi].p());

		models[1      ].update(hi>>3&1);
		models[hi >> 3].update(hi>>2&1);
		models[hi >> 2].update(hi>>1&1);
		models[hi >> 1].update(hi   &1);

		BitModelFast* lower = &models[15*(hi-15)];

		lo += lo + e.decode(lower[lo].p());
		lo += lo + e.decode(lower[lo].p());
		lo += lo + e.decode(lower[lo].p());
		lo += lo + e.decode(lower[lo].p());

		lower[1      ].update(lo>>3&1);
		lower[lo >> 3].update(lo>>2&1);
		lower[lo >> 2].update(lo>>1&1);
		lower[lo >> 1].update(lo   &1);

		return (hi<<4) + lo - (256+16);
	}
};

struct ByteModelBitwiseSmall
{
	BitModelSmall models[257];
	
	template<typename Coder>
	void encode(Coder& e, int c)
	{
		// code high 4 bits in contexts cxt+1..15
		int b = (c>>4) + 16;

		e.encode(b>>3&1, models[1].p());
		e.encode(b>>2&1, models[b >> 3].p());
		e.encode(b>>1&1, models[b >> 2].p());
		e.encode(b   &1, models[b >> 1].p());

		models[1     ].update(b>>3&1);
		models[b >> 3].update(b>>2&1);
		models[b >> 2].update(b>>1&1);
		models[b >> 1].update(b   &1);

		BitModelSmall* lower = &models[15*(b-15)];

		b = (c&15) + 16;
		e.encode(b>>3&1, lower[1].p());
		e.encode(b>>2&1, lower[b >> 3].p());
		e.encode(b>>1&1, lower[b >> 2].p());
		e.encode(b   &1, lower[b >> 1].p());

		lower[1     ].update(b>>3&1);
		lower[b >> 3].update(b>>2&1);
		lower[b >> 2].update(b>>1&1);
		lower[b >> 1].update(b   &1);
	}

	template<typename Decoder>
	int decode(Decoder& e)
	{
		// code high 4 bits in contexts cxt+1..15
		int hi = 1, lo = 1;

		hi += hi + e.decode(models[1].p());
		hi += hi + e.decode(models[hi].p());
		hi += hi + e.decode(models[hi].p());
		hi += hi + e.decode(models[hi].p());

		models[1      ].update(hi>>3&1);
		models[hi >> 3].update(hi>>2&1);
		models[hi >> 2].update(hi>>1&1);
		models[hi >> 1].update(hi   &1);

		BitModelSmall* lower = &models[15*(hi-15)];

		lo += lo + e.decode(lower[lo].p());
		lo += lo + e.decode(lower[lo].p());
		lo += lo + e.decode(lower[lo].p());
		lo += lo + e.decode(lower[lo].p());

		lower[1      ].update(lo>>3&1);
		lower[lo >> 3].update(lo>>2&1);
		lower[lo >> 2].update(lo>>1&1);
		lower[lo >> 1].update(lo   &1);

		return (hi<<4) + lo - (256+16);
	}
};

struct NibbleModelMultiSymbol
{
	uint32 sums[16*2];

	NibbleModelMultiSymbol()
	{
		for(int i = 0; i < 32; ++i)
			sums[i] = 0;

		for(int i = 0; i < 16; ++i)
			update(i);
	}

	
	void update(int c)
	{
		uint32 ic = ~c;
		c |= 16;

		#define UPDATEPART(bit) sums[c >> ((bit)+1)] += (ic >> (bit)) & 1

		++sums[0];
		UPDATEPART(3); UPDATEPART(2); UPDATEPART(1); UPDATEPART(0);
		++sums[c];

		#undef UPDATEPART
	}

	void rescale()
	{
		for(int i = 0; i < 16; ++i)
		{
			sums[i] = 0;
		}

		for(int i = 16; i < 32; ++i)
		{
			uint32 old = sums[i];

			uint32 ic = ~(i & 0xf);

			uint32 scaled = old >> 1;
			scaled += scaled == 0;

			sums[i] = scaled;

			sums[0] += scaled;

			#define UPDATEPART(bit) sums[i >> (bit+1)] += (ic >> (bit)) & 1;

			UPDATEPART(3); UPDATEPART(2); UPDATEPART(1); UPDATEPART(0);

			#undef UPDATEPART
		}
	}

	template<typename Coder>
	void encode(Coder& e, int c)
	{
		uint32 ic = ~c;
		c |= 16;

		uint32 count = sums[c];
		uint32 total = sums[0];

		assert(count > 0);

		#define ADDPART(bit) s += sums[c >> (bit+1)] & (int32(c << (31-(bit))) >> 31)

		// Calculate cumulative
		uint32 s = 0;
		ADDPART(3); ADDPART(2); ADDPART(1); ADDPART(0);

		if(total >= (1<<23))
			rescale();

		#undef ADDPART

		#define UPDATEPART(bit) sums[c >> (bit+1)] += (ic >> (bit)) & 1;

		// Update
		++sums[0];
		UPDATEPART(3); UPDATEPART(2); UPDATEPART(1); UPDATEPART(0);
		++sums[c];

		#undef UPDATEPART
		
		e.encode_range(s, count, total);
	}
};

struct ByteModelMultiSymbol
{
	uint32 sums[256*2];

	ByteModelMultiSymbol()
	{
		for(int i = 0; i < 512; ++i)
			sums[i] = 0;

		for(int i = 0; i < 256; ++i)
			update(i);
	}

	void update(int c)
	{
		uint32 ic = ~c;
		c |= 256;

		#define UPDATEPART(bit) sums[c >> (bit+1)] += (ic >> (bit)) & 1

		++sums[0];
		UPDATEPART(7); UPDATEPART(6); UPDATEPART(5); UPDATEPART(4);
		UPDATEPART(3); UPDATEPART(2); UPDATEPART(1); UPDATEPART(0);
		++sums[c];

		#undef UPDATEPART
	}

	void rescale()
	{
		//printf("Rescale!\n");

		for(int i = 0; i < 256; ++i)
		{
			sums[i] = 0;
		}

		for(int i = 256; i < 512; ++i)
		{
			uint32 old = sums[i];

			uint32 ic = ~(i & 0xff);

			uint32 scaled = old >> 1;
			scaled += scaled == 0;

			sums[i] = scaled;

			sums[0] += scaled;

			#define UPDATEPART(bit) sums[i >> (bit+1)] += scaled & (int32(ic << (31-bit)) >> 31)

			UPDATEPART(7); UPDATEPART(6); UPDATEPART(5); UPDATEPART(4);
			UPDATEPART(3); UPDATEPART(2); UPDATEPART(1); UPDATEPART(0);

			#undef UPDATEPART
		}
	}

	template<typename Decoder>
	int decode(Decoder& e)
	{
		if(sums[0] >= (1<<16))
			rescale();

		uint32 total = sums[0];
		uint32 cnt = e.get_count(total);

		uint32 c = 1;
		uint32 s = 0;
		#define EXTRACTBIT() { int over = (cnt >= s + sums[c]); s += sums[c] & -over; c = (c << 1) + over; }

		EXTRACTBIT(); EXTRACTBIT(); EXTRACTBIT(); EXTRACTBIT();
		EXTRACTBIT(); EXTRACTBIT(); EXTRACTBIT(); EXTRACTBIT();

		e.decoded_range(s, sums[c]);

		c &= 0xff;

		update(c);

		return c;
	}

	template<typename Coder>
	void encode(Coder& e, int c)
	{
		if(sums[0] >= (1<<16))
			rescale();

		uint32 ic = ~c;
		c |= 256;

		uint32 count = sums[c];
		uint32 total = sums[0];

		assert(count > 0);

		#define ADDPART(bit) s += sums[c >> (bit+1)] & (int32(c << (31-(bit))) >> 31)

		// Calculate cumulative
		uint32 s = 0;
		ADDPART(7); ADDPART(6); ADDPART(5); ADDPART(4);
		ADDPART(3); ADDPART(2); ADDPART(1); ADDPART(0);

		#undef ADDPART

		#define UPDATEPART(bit) sums[c >> (bit+1)] += (ic >> (bit)) & 1;

		// Update
		++sums[0];
		UPDATEPART(7); UPDATEPART(6); UPDATEPART(5); UPDATEPART(4);
		UPDATEPART(3); UPDATEPART(2); UPDATEPART(1); UPDATEPART(0);
		++sums[c];

		#undef UPDATEPART
		
		e.encode_range(s, count, total);
	}
};

template<int Symbols = 256>
struct ByteModelNaive
{
	uint32 count[Symbols];
	uint32 accum[Symbols];
	uint32 total;

	ByteModelNaive()
	{
		for(int i = 0; i < Symbols; ++i)
		{
			count[i] = 1;
			accum[i] = i;
		}

		total = Symbols;
	}

	void rescale()
	{
		for(int i = 0; i < Symbols; ++i)
		{
			uint32 old = count[i];

			uint32 scaled = old >> 1;
			scaled += scaled == 0;

			count[i] = scaled;
		}

		total = 0;
		for(int i = 0; i < Symbols; ++i)
		{
			accum[i] = total;
			total += count[i];
		}
	}

	template<typename Coder>
	void encode(Coder& e, int c)
	{
		uint32 cnt = count[c]++;
		uint32 cm = accum[c];

		assert(cnt > 0);

		for(int i = c + 1; i < Symbols; ++i)
			++accum[i];

		e.encode_range(cm, cnt, total);

		if(++total >= (1<<16))
			rescale();
	}
};

struct ByteModelNibble
{
	ByteModelNaive<16> upper;
	ByteModelNaive<16> lower[16];

	template<typename Coder>
	void encode(Coder& e, int c)
	{
		upper.encode(e, c >> 4);
		lower[c >> 4].encode(e, c & 0xf);
	}
};

struct ByteModelNibbleMultiSymbol
{
	NibbleModelMultiSymbol upper;
	NibbleModelMultiSymbol lower[16];

	template<typename Coder>
	void encode(Coder& e, int c)
	{
		upper.encode(e, c >> 4);
		lower[c >> 4].encode(e, c & 0xf);
	}
};


struct ByteModelSpan
{
	uint32 count[256];
	uint32 lastAccum;
	int lastSymbol;
	uint32 total;

	ByteModelSpan()
	{
		for(int i = 0; i < 256; ++i)
		{
			count[i] = 1;
		}

		total = 256;
		lastAccum = 0;
		lastSymbol = 0;
	}

	void rescale()
	{
		total = 0;
		for(int i = 0; i < 256; ++i)
		{
			uint32 old = count[i];

			uint32 scaled = old >> 1;
			scaled += scaled == 0;

			count[i] = scaled;
			total += scaled;
		}

		lastAccum = 0;
		lastSymbol = 0;
	}

	template<typename Coder>
	void encode(Coder& e, int c)
	{
		uint32 cnt = count[c];
		uint32 cm = lastAccum;

		if(c > lastSymbol)
		{
			for(int i = lastSymbol; i < c; ++i)
				cm += count[i];
		}
		else if(c < lastSymbol)
		{
			for(int i = c; i < lastSymbol; ++i)
				cm -= count[i];
		}

		e.encode_range(cm, cnt, total);

		++count[c];

		lastAccum = cm;
		lastSymbol = c;

		if(++total >= (1<<16))
			rescale();
	}
};

#endif // UUID_F41E4A110DB24E636A5271A33C937B46
